package LC05;

import java.util.Arrays;

public class LC0416 {
    public static void main(String[] args) {
        System.out.println(canPartition(new int[]{1, 2, 3, 4, 5, 6, 7}));
    }

    public static boolean canPartition(int[] nums) {
        int length = nums.length;
        if (length < 2) {
            return false;
        }
        int s = 0;
        for (int num : nums) {
            s += num;
        }
        if (s % 2 == 1) {
            return false;
        }
        int s2 = s / 2;

        boolean[][] arr = new boolean[length][s2 + 1];
        if (nums[0] <= s2) {
            arr[0][nums[0]] = true;
        }

        for (int i = 1; i < length; i++) {
            int a = 0;
            for (int j = 0; j <= s2; j++) {
                arr[i][j] = arr[i - 1][j];
                if (nums[i] == j) {
                    arr[i][j] = true;
                    continue;
                }
                if (nums[i] < j) {
                    arr[i][j] = arr[i - 1][j] || arr[i - 1][j - nums[i]];
                }
            }
        }

        return arr[length - 1][s2];
    }
}
